Ông sinh tại làng Trung Sơn, huyện Hòa Vang, tỉnh Quảng Nam (nay là xã Hòa Liên, huyện Hòa Vang, thành phố Đà Nẵng).
Nguyễn Bá Phát lớn lên trong một gia đình nghèo, cha là một nhà nho có tinh thần yêu nước, dạy chữ Hán có tiếng trong vùng. Năm 18 tuổi, phần vì chỉ học chữ quốc ngữ, phần vì có những chuyện không hay trong tộc họ, Phát bỏ đi đăng lính thủy thủ vào các tàu Pháp (1939). Sáu năm lênh đênh trên biển cả, anh đã đi đến nhiều bờ biển châu Á, châu Phi, qua tận đảo Réunion hay Madagascar. Trong các câu lạc bộ thủy thủ, anh được nghe bao điều, từ cộng sản đến xã hội, tự do đến cách mạng và nhiều thông tin ở quê nhà.
